#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution {
public:
	vector<string> result;
	vector<string> wordBreak(string s, vector<string>& wordDict) {
		backtracking(s, wordDict, "");
		return result;
	}

	void backtracking(string s, vector<string>& wordDict, string sentence) {
		if (s == "") {
			sentence.erase(sentence.end() - 1);
			result.push_back(sentence);
			return;
		}
		for (int i = 0; i < s.size(); i++) {
			string str = s.substr(0, i + 1);
			const auto& it = find(wordDict.begin(), wordDict.end(), str);
			if (it != wordDict.end()) {
				string temp = sentence;
				sentence=sentence+str+" ";
				backtracking(s.substr(i + 1), wordDict,sentence);
				sentence = temp;
			}
		}
	}
};

int main() {
	//string a = "1234";
	//cout << a << endl;
	//a.erase(a.end() - 1);
	//cout << a << endl;
	Solution s;
	string str = "aaaaaaa";
	vector<string> arr = { "aaa","aaaa" };
	s.wordBreak(str, arr);
}